import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/8 17:15
 * @description 设 f[i][j]表示只能放前i个物品的情况下，容量为j的背包所能达到的最大价值
 * 朴素做法：对于第i个物品，枚举其选了多少来转移，时间复杂度为 O(n^3), 同样取或不取，但是这次可以取n次
 * 优化后，转移方程为 f[i][j] = max(f[i-1][j]， f[i][j-wi] + vi)；
 *
 */
public class Solution {
    public static void main(String[] args) {

    }
    int n, W;
    int[] w, v;
    int[] f;
    public void dp() {
        for (int i = 1; i <= n; i++) {
            for (int l = w[i]; l <= W; l++) {
                // 正向转移，假设取这个物品，那么 f[i][j-wi]是由 f[i][j-2*w[i]]转移而来，
                f[l] = Math.max(f[l], f[l-w[i]] + v[i]);
            }
        }
    }
}
